package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.List;

import org.junit.Assert;

import com.leetcode.algorithm.common.Node;
import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)589. N叉树的前序遍历
 * (done)590. N叉树的后序遍历
 * (done)429. N叉树的层序遍历
 * (done)559. N叉树的最大深度
 * (done)110. 平衡二叉树
 * (done)606. 根据二叉树创建字符串
 * @author: jie.deng
 * @time: 2019年1月18日 下午1:30:18
 */
public class MySolution0118 {
	
    /**
     * 589. N叉树的前序遍历
     * 
	 * 给定一个 N 叉树，返回其节点值的前序遍历。
	 * 例如，给定一个 3叉树 :
	 * 返回其前序遍历: [1,3,5,6,2,4]。
     * @param root
     * @return
     */
	public List<Integer> preorder(Node root) {
    	List<Integer> list = new ArrayList<Integer>();
    	preorder(root, list);
		return list;
	}

	private void preorder(Node node, List<Integer> list) {
		if (node != null) {
			list.add(node.val);
			List<Node> children = node.children;
			if (children != null) {
				for (Node child : children) {
					preorder(child, list);
				}
			}
		}
	}

	/**
     * 590. N叉树的后序遍历
     * 
	 * 给定一个 N 叉树，返回其节点值的后序遍历。
	 * 例如，给定一个 3叉树 :
	 * 返回其后序遍历: [5,6,3,2,4,1].
     * @param root
     * @return
     */
	public List<Integer> postorder(Node root) {
		List<Integer> list = new ArrayList<Integer>();
		postorder(root, list);
		return list;
	}

	private void postorder(Node node, List<Integer> list) {
		if (node != null) {
			List<Node> children = node.children;
			if (children != null) {
				for (Node child : children) {
					postorder(child, list);
				}
			}
			list.add(node.val);
		}
	}

	/**
     * 429. N叉树的层序遍历
     * 
     * 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
     * 
     * 例如，给定一个 3叉树 :
     * 返回其层序遍历:
     * [
     *      [1],
     *      [3,2,4],
     *      [5,6]
     * ]
     * 
     * 说明:
     * 树的深度不会超过 1000。
     * 树的节点总数不会超过 5000。
     * @param root
     * @return
     */
	public List<List<Integer>> levelOrder(Node root) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		levelOrder(root, 0, list);
		return list;
	}

	private void levelOrder(Node node, int level, List<List<Integer>> list) {
		if (node != null) {
			List<Integer> levelList = null;
			if (list.size() > level) {
				levelList = list.get(level);
			} else {
				levelList = new ArrayList<Integer>();
				list.add(levelList);
			}
			levelList.add(node.val);
			
			List<Node> children = node.children;
			if (children != null) {
				for (Node child : children) {
					levelOrder(child, level + 1, list);
				}
			}
		}
	}
	
	
	/**
	 * 559. N叉树的最大深度
	 * 
	 * 给定一个 N 叉树，找到其最大深度。
	 * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
	 * 
	 * 例如，给定一个 3叉树 :
	 * 我们应返回其最大深度，3。
	 * 
	 * 说明:
	 * 
	 * 树的深度不会超过 1000。
	 * 树的节点总不会超过 5000。
	 * @param root
	 * @return
	 */
	public int maxDepth(Node root) {
		int dept = 0;
		if (root != null) {
			dept = maxDepth(root, 1);
		}
		return dept;
	}

	private int maxDepth(Node node, int depth) {
		Assert.assertNotNull(node);
		List<Node> children = node.children;
		if (children != null) {
			int max = depth;
			for (Node child : children) {
				if (child != null) {
					int childDepth = maxDepth(child, depth + 1);
					if (childDepth > max) {
						max = childDepth;
					}
				}
			}
			depth = max;
		}
		return depth;
	}

	/**
	 * 110. 平衡二叉树
	 * 
	 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
	 * 
	 * 本题中，一棵高度平衡二叉树定义为：
	 * 
	 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
	 * 
	 * 示例 1:
	 * 
	 * 给定二叉树 [3,9,20,null,null,15,7]
	 * 
	 *     3
	 *    / \
	 *   9  20
	 *     /  \
	 *    15   7
	 * 返回 true 。
	 * 
	 * 示例 2:
	 * 
	 * 给定二叉树 [1,2,2,3,3,null,null,4,4]
	 * 
	 *        1
	 *       / \
	 *      2   2
	 *     / \
	 *    3   3
	 *   / \
	 *  4   4
	 * 返回 false 。
	 * @param root
	 * @return
	 */
	public boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isBalanced(root.left, root.right, 1) > 0;
	}

	/**
	 * 若平衡二叉树,返回结点的深度(包含当前节点到根结点的深度)；若非平衡二叉树，返回0。
	 * 
	 * @param left
	 * @param right
	 * @param depth
	 * @return
	 */
	private int isBalanced(TreeNode left, TreeNode right, int depth) {
		int depthLeft = depth;
		int depthRight = depth;
		if (left != null) {
			depthLeft = isBalanced(left.left, left.right, depth + 1);
			if (depthLeft == 0) {
				return 0;
			}
		}
		if (right != null) {
			depthRight = isBalanced(right.left, right.right, depth + 1);
			if (depthRight == 0) {
				return 0;
			}
		}
		if (Math.abs(depthLeft - depthRight) > 1) {
			return -1;
		}
		return Math.max(depthLeft, depthRight);
	}

	
	/**
	 * 606. 根据二叉树创建字符串
	 * 
	 * 你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
	 * 
	 * 空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
	 * 
	 * 示例 1:
	 * 
	 * 输入: 二叉树: [1,2,3,4]
	 *        1
	 *      /   \
	 *     2     3
	 *    /    
	 *   4     
	 * 
	 * 输出: "1(2(4))(3)"
	 * 
	 * 解释: 原本将是“1(2(4)())(3())”，
	 * 在你省略所有不必要的空括号对之后，
	 * 它将是“1(2(4))(3)”。
	 * 示例 2:
	 * 
	 * 输入: 二叉树: [1,2,3,null,4]
	 *        1
	 *      /   \
	 *     2     3
	 *      \  
	 *       4 
	 * 
	 * 输出: "1(2()(4))(3)"
	 * 
	 * 解释: 和第一个示例相似，
	 * 除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
	 * @param t
	 * @return
	 */
	public String tree2str(TreeNode t) {
		StringBuilder sbStr = new StringBuilder();
		if (t != null) {
			tree2str(t, sbStr);
		}
		return sbStr.toString();
	}

	private void tree2str(TreeNode t, StringBuilder sbStr) {
		Assert.assertNotNull(t);
		Assert.assertNotNull(sbStr);
		sbStr.append(t.val);
		if (t.left != null) {
			sbStr.append("(");
			tree2str(t.left, sbStr);
			sbStr.append(")");
		}
		if (t.right != null) {
			if (t.left == null) {
				sbStr.append("()");
			}
			sbStr.append("(");
			tree2str(t.right, sbStr);
			sbStr.append(")");
		}
	}
    
    
}
